iT邦幫忙

2024 iThome 鐵人賽

DAY 22
1

引言

在我們前面的文章中,我們探討了以「分治法」為基礎的排序演算法,例如快速排序和合併排序,並展示了它們如何在前端特效應用中進行視覺化處理。然而,除了分治法,另一個經典且高效的排序演算法是「堆排序」(Heap Sort),它基於完全二元樹的特性來進行排序操作。

今天,我們將介紹堆排序的基本概念,並通過程式碼逐步展示其視覺化實作。這篇文章將重點放在演算法步驟的動畫化處理,讓你看到如何在前端動畫系統中以直觀方式呈現堆排序。

https://ithelp.ithome.com.tw/upload/images/20241005/20135197D5PSky96wh.png

線上查看動畫效果

二元樹結構

我們先來介紹資料結構,這個結構的好處是,可以利用陣列來儲存節點,並且透過一個簡單的索引規則找到每個父節點的子節點。並限定每個節點最多擁有兩個子節點,所有層的節點都是從左至右排列緊密的。

索引規則

  • 每個節點 𝑖 的左子節點的索引值為:2 × 𝑖 + 1
  • 每個節點 𝑖 的右子節點的索引值為:2 × 𝑖 + 2

假設我們有一個包含 7 個節點的完全二元樹,可以將其用陣列表示為:
[黃0,紅1,紅2,藍3,藍4,藍5,藍6]

其中三個顏色分別代表不同階層

  1. 根節點(黃0)是陣列中的第 0 個元素,它的兩個子節點是:
    • 紅1:2 × 0 + 1 = 1
    • 紅2:2 × 0 + 2 = 2
  2. 節點(紅1)是第 1 個元素,它的兩個子節點是:
    • 藍3:2 × 1 + 1 = 3
    • 藍4:2 × 1 + 2 = 4
  3. 節點(紅2)是第 2 個元素,它的兩個子節點是:
    • 藍5:2 × 2 + 1 = 5
    • 藍6:2 × 2 + 2 = 6

堆排序

堆排序的核心概念是通過建立最大堆來將數列進行排序。在最大堆中,每個父節點的值都大於或等於其子節點的值。接著,我們通過反覆將最大堆的堆頂元素移到陣列末端,並對剩餘的部分重新調整堆,來完成排序過程。

function heapSort(arr) {
    const n = arr.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i);
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
    return arr;
}

function heapify(arr, n, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

這個方法的聰明之處在於,建立好最大堆後,我們僅僅把最大值和末尾進行交換,此時我們只需要找到下一個最大值,並通過層層交換把它擺上最上層,就再一次完成最大堆的排序了。

迭代方程式

為了實現動畫效果,我們將堆排序的過程分為三個階段:建堆交換、和排序。在這裡,利用和前幾次相同的狀態管理架構,並透過不同的階段來逐步呈現視覺化動畫效果。這樣的設計可以讓每個排序步驟清晰可見,並允許我們控制動畫的進度。

class SortAlgorithm{
    heapSortSetting(columns){
        this.i = Math.floor(columns.length / 2) - 1;
        this.j = this.i;
        this.heapPhase = "1.build";
    }
    heapSort(columns){
        const len = columns.length;
        const i = this.i;
        const j = this.j;
        switch(this.heapPhase){
            case "1.build":
            case "2.swap":
            case "3.sort":
        }
    }
}

階段1:建堆

在建堆階段,我們將從數列的中間偏左開始,向左逐步對每個節點進行 heapify,將其轉換為最大堆。如果所有節點都已處理完,我們會進入下一階段,開始交換。

case "1.build":
    this.j = SortAlgorithm.heapify(columns, len, j);
    if(this.j == -1){
        this.i--;
        this.j = this.i;
        if(this.i < 0){
            this.i = len - 1;
            this.j = 0;
            this.heapPhase = "2.swap";
        }
    }
    break;

選在中間相當於從二元樹的最底層開始,當它儲存在陣列中,表示最後一組父子關係的索引值是[中間, 中間 * 2 +1, 中間 * 2 + 2]

階段2:交換

在交換階段,我們將堆頂的最大元素與陣列末端的元素交換,這樣最大值就被移到了陣列的正確位置。

case "2.swap":
    const a = columns[0];
    const b = columns[i];
    SortAlgorithm.swapColumn(a, b, 60);
    this.heapPhase = "3.sort";
    break;

階段3:排序

最後,我們對剩餘的部分再次進行 heapify,並重複上一步驟,直到所有元素都已排序完成。

case "3.sort":
    this.j = SortAlgorithm.heapify(columns, i, j);
    if(this.j == -1){
        this.j = 0;
        this.i--;
        this.heapPhase = "2.swap";
        if(this.i < 0) return true;
    }
    break;

Heapify 函式實作

建堆的方式和範例程式碼相同,要注意的地方在於,在不能使用遞迴的前提下,我們利用回傳值來進行下一次的 heapify,以此達到迭代的效果。

class SortAlgorithm{
    static heapify(columns, len, i){
        let largest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < len && columns[left].height > columns[largest].height) {
            largest = left;
        }
        if (right < len && columns[right].height > columns[largest].height) {
            largest = right;
        }
        if (largest !== i) {
            const a = columns[i];
            const b = columns[largest];
            SortAlgorithm.swapColumn(a, b, 60);
            return largest;
        }
        return -1;
    }
}

這邊可以特別強調的是,二元樹的空間大小是 2^n - 1,我們的資料有可能小於這個空間,因此,在 heapify 的時候會先檢查子節點是否存在,是否超出陣列範圍

迭代器和生成器

接下來讓我們介紹如何使用生成器(Generators)來實作 堆排序(Heap Sort) 的迭代版本,簡直是不費吹灰之力,就從範例程式碼改成我們所需的視覺化版本了!

主要階段

生成器在 JavaScript 中是一種特殊的函數,允許函數的執行被暫停和恢復,並可以在每次呼叫 yield 時返回當前狀態。在這裡負責執行兩個主要階段:建堆排序

class SortAlgorithmIterable{
    * heapSortMaker(columns) {
        const n = columns.length;
        for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
            yield* this.heapify(columns, n, i);
        }
        for (let i = n - 1; i > 0; i--) {
            const a = columns[0];
            const b = columns[i];
            SortAlgorithm.swapColumn(a, b, 60);
            yield* this.heapify(columns, i, 0);
        }
        yield true;
    }
}

Heapify

和前面邏輯相同,在這裡我們不需要通過回傳值來手動迭代,可以透過 yield* 來呼叫遞迴函式。

class SortAlgorithmIterable{
    * heapify(columns, n, i) {
        yield false;
        let largest = i;
        let left = 2 * i + 1;
        let right = 2 * i + 2;
        if (left < n && columns[left].height > columns[largest].height) largest = left;
        if (right < n && columns[right].height > columns[largest].height) largest = right;
        if (largest !== i) {
            const a = columns[largest];
            const b = columns[i];
            SortAlgorithm.swapColumn(a, b, 60);
            yield* this.heapify(columns, n, largest);
        }
    }
}

結論

堆排序的程式碼雖然簡潔,空間概念相對來說比其他排序演算法要稍微複雜一些,因為它涉及到樹狀結構的調整和多階段的操作。儘管如此,我們仍然可以通過合理的狀態機設計,將每個步驟逐一展現,並保持排序的可視化和動畫效果。

而基於生成器的堆排序不僅能夠保留原本演算法的結構,還可以清晰地觀察每個排序步驟,讓我們對演算法的內部運作有了更具體的理解。隨著生成器的應用,動畫化的遞迴流程變得更加輕鬆和高效,展示了生成器在處理複雜邏輯的靈活性。


上一篇
C6 合併排序的舞步-視覺化演繹分治法的魅力
下一篇
D0 再出發:寫作與 AI 的心路歷程,為創作新篇章蓄力
系列文
讓演算法起舞:前端特效應用的探索之旅35
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言